﻿// 3548. 双端队列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/3551/

给定一个双端队列，初始时队列为空。

你要对其进行 q 次操作，每次操作可能是以下三种之一：

L x，从队列的左端插入整数 x。
R x，从队列的右端插入整数 x。
? x，请你计算为了使已经处于队列中的整数 x 位于队列的最左端或最右端，至少需要从最左端或最右端弹出多少个数字。
保证操作 3 一定合法（ ? x 中的 x 一定已经处于队列之中）。

每个数字最多被插入到队列中 1 次（队列中一定不会存在重复数字）。

注意，操作 3 只是询问最少需要弹出多少数字，不是真的要弹出它们，队列中的数字始终不会减少。

输入格式
第一行包含整数 q。

接下来 q 行，每行包含一个操作信息，格式如题所述。

输出格式
对于每个操作 3，输出一行，一个整数表示结果。

数据范围
对于 30% 的数据，1≤q≤30,1≤x≤30。
对于 100% 的数据，1≤q≤2×105,1≤x≤2×105。
保证至少包含一个操作 3，
保证操作 1 和 2 不会重复插入数字。
保证操作 3 不会询问队列中不存在的数字。

输入样例1：
8
L 1
R 2
R 3
? 2
L 4
? 1
L 5
? 1
输出样例1：
1
1
2
输入样例2：
10
L 100
R 100000
R 123
L 101
? 123
L 10
R 115
? 100
R 110
? 115
输出样例2：
0
2
1



*/


#include <iostream>
#include <deque>
#include <unordered_map>
#include <stack>


using namespace std;

const int N = 200010;
struct OP {
	string op;
	int n;
}ops[N];

int n;

int main()
{
	cin >> n;
	stack<int> stl, str;
	unordered_map<int,int> mml, mmr;

	for (int i = 0; i < n; i++) {
		cin >> ops[i].op >> ops[i].n;
		if (ops[i].op == "L") {
			stl.push(ops[i].n);
			mml[ops[i].n] = stl.size();
		}
		else if (ops[i].op == "R") {
			str.push(ops[i].n);
			mmr[ops[i].n] = str.size();
		}
		else {
			int v = ops[i].n;
			if (mml.count(v)) {
				cout << min(stl.size() - mml[v], str.size()+mml[v]-1) << endl;
			}
			else {
				cout << min(str.size() - mmr[v], stl.size()+mmr[v]-1) << endl;
			}
		}
	}

	return 0;
}

 